package com.yanceysong.codetop.s81_s90;

/**
 * .@ClassName S86_Mid_62_不同路径
 * .@Description
 * .@date 2024/6/5 下午3:36
 * .@Author yanceysong
 * .@Version 1.0
 */
public class S86_Mid_62_不同路径 {

    /**
     * .S86_Mid_62_不同路径
     * .<p>
     * .<a href="https://leetcode.cn/problems/unique-paths/">...</a>
     * .<p>
     * .一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 "Start" ）。
     * .<p>
     * .机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 "Finish" ）。
     * .<p>
     * .问总共有多少条不同的路径？
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：m = 3, n = 7
     * .输出：28
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：m = 3, n = 2
     * .输出：3
     * .解释：
     * .从左上角开始，总共有 3 条路径可以到达右下角。
     * .1. 向右 -> 向下 -> 向下
     * .2. 向下 -> 向下 -> 向右
     * .3. 向下 -> 向右 -> 向下
     * .<p>
     * .示例 3：
     * .<p>
     * .输入：m = 7, n = 3
     * .输出：28
     * .<p>
     * .示例 4：
     * .<p>
     * .输入：m = 3, n = 3
     * .输出：6
     * .<p>
     * .提示：
     * .<p>
     * .1 <= m, n <= 100
     * .题目数据保证答案小于等于 2 * .10^9
     * .<p>
     * .核心标签：动态规划、数学（组合数学）
     * .<p>
     * .解题思路：
     * .这是一个经典的动态规划问题，也可以用组合数学求解。
     * .<p>
     * .方法一：动态规划（本实现采用）
     * .<p>
     * .状态定义：
     * .dp[i][j] 表示从起点 (0,0) 到达位置 (i,j) 的不同路径数量
     * .<p>
     * .状态转移方程：
     * .dp[i][j] = dp[i-1][j] + dp[i][j-1]
     * .<p>
     * .解释：到达 (i,j) 只有两种方式：
     * .1. 从上方 (i-1,j) 向下移动
     * .2. 从左方 (i,j-1) 向右移动
     * .<p>
     * .初始化：
     * .- 第一行：dp[0][j] = 1（只能一直向右）
     * .- 第一列：dp[i][0] = 1（只能一直向下）
     * .<p>
     * .方法二：组合数学（优化解法）
     * .从 (0,0) 到 (m-1,n-1) 需要：
     * .- 向下移动 m-1 步
     * .- 向右移动 n-1 步
     * .- 总共 m+n-2 步
     * .<p>
     * .问题转化为：从 m+n-2 步中选择 m-1 步向下（或 n-1 步向右）
     * .答案 = C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * .(n-1)!)
     * .<p>
     * .关键洞察：
     * .1. 这是一个无后效性问题，当前状态只依赖于之前的状态
     * .2. 边界情况：第一行和第一列只有一条路径
     * .3. 可以优化空间复杂度到 O(n)，使用滚动数组
     * .<p>
     * .ASCII 图解示例：
     * .<p>
     * .示例 1：m = 3, n = 2
     * .<p>
     * .网格示意图（S=Start, F=Finish）：
     * .<p>
     * .    0   1
     * .  ┌───┬───┐
     * .0 │ S │   │
     * .  ├───┼───┤
     * .1 │   │   │
     * .  ├───┼───┤
     * .2 │   │ F │
     * .  └───┴───┘
     * .<p>
     * .三条不同的路径：
     * .<p>
     * .路径1: 右 → 下 → 下
     * .    0   1
     * .  ┌───┬───┐
     * .0 │ S → 1 │
     * .  ├───┼───┤
     * .1 │   │ ↓ │
     * .  ├───┼───┤
     * .2 │   │ F │
     * .  └───┴───┘
     * .<p>
     * .路径2: 下 → 右 → 下
     * .    0   1
     * .  ┌───┬───┐
     * .0 │ S │   │
     * .  ├───┼───┤
     * .1 │ ↓ → 2 │
     * .  ├───┼───┤
     * .2 │   │ F │
     * .  └───┴───┘
     * .<p>
     * .路径3: 下 → 下 → 右
     * .    0   1
     * .  ┌───┬───┐
     * .0 │ S │   │
     * .  ├───┼───┤
     * .1 │ ↓ │   │
     * .  ├───┼───┤
     * .2 │ 3 → F │
     * .  └───┴───┘
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .动态规划过程（m = 3, n = 2）：
     * .<p>
     * .步骤1：初始化第一行和第一列
     * .<p>
     * .    j=0  j=1
     * .  ┌────┬────┐
     * .i=0│ 1  │ 1  │  ← 第一行全为1（只能向右）
     * .  ├────┼────┤
     * .i=1│ 1  │ ?  │
     * .  ├────┼────┤
     * .i=2│ 1  │ ?  │  ← 第一列全为1（只能向下）
     * .  └────┴────┘
     * .<p>
     * .步骤2：填充 dp[1][1]
     * .dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
     * .<p>
     * .    j=0  j=1
     * .  ┌────┬────┐
     * .i=0│ 1  │ 1  │
     * .  ├────┼────┤
     * .i=1│ 1  │ 2  │  ← 从上方(1)和左方(1)到达
     * .  ├────┼────┤
     * .i=2│ 1  │ ?  │
     * .  └────┴────┘
     * .<p>
     * .步骤3：填充 dp[2][1]
     * .dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
     * .<p>
     * .    j=0  j=1
     * .  ┌────┬────┐
     * .i=0│ 1  │ 1  │
     * .  ├────┼────┤
     * .i=1│ 1  │ 2  │
     * .  ├────┼────┤
     * .i=2│ 1  │ 3  │  ← 从上方(2)和左方(1)到达
     * .  └────┴────┘
     * .<p>
     * .最终答案：dp[2][1] = 3
     * .<p>
     * .═══════════════════════════════════════════════════════════════
     * .<p>
     * .更大的示例（m = 3, n = 3）：
     * .<p>
     * .    j=0  j=1  j=2
     * .  ┌────┬────┬────┐
     * .i=0│ 1  │ 1  │ 1  │  ← 第一行：只能向右
     * .  ├────┼────┼────┤
     * .i=1│ 1  │ 2  │ 3  │  ← dp[1][1]=1+1=2, dp[1][2]=2+1=3
     * .  ├────┼────┼────┤
     * .i=2│ 1  │ 3  │ 6  │  ← dp[2][1]=2+1=3, dp[2][2]=3+3=6
     * .  └────┴────┴────┘
     * .    ↑
     * .  第一列：只能向下
     * .<p>
     * .计算过程：
     * .dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
     * .dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
     * .dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
     * .dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
     * .<p>
     * .最终答案：6
     * .<p>
     * .时间复杂度：O(m * .n)
     * .- 需要填充 m * .n 的二维数组
     * .- 每个位置计算一次
     * .<p>
     * .空间复杂度：O(m * .n)
     * .- 需要 m * .n 的二维数组存储中间结果
     * .- 可以优化到 O(n)，使用滚动数组（只保留上一行的数据）
     */
    public int uniquePaths(int m, int n) {
        // 创建 dp 数组，dp[i][j] 表示到达位置 (i,j) 的路径数
        int[][] dp = new int[m][n];

        // 初始化第一行：从 (0,0) 到第一行的任意位置只有一条路径（一直向右）
        for (int col = 0; col < n; col++) {
            dp[0][col] = 1;
        }

        // 初始化第一列：从 (0,0) 到第一列的任意位置只有一条路径（一直向下）
        for (int row = 0; row < m; row++) {
            dp[row][0] = 1;
        }

        // 填充 dp 数组：从 (1,1) 开始
        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                // 到达 (row, col) 的路径数 = 从上方来的路径数 + 从左方来的路径数
                dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
            }
        }

        // 返回右下角的路径数
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        S86_Mid_62_不同路径 solution = new S86_Mid_62_不同路径();

        System.out.println("=== 不同路径测试开始 ===");

        // 测试1: 示例1 - 3x7网格
        System.out.println("\n--- 测试1: 示例1 m=3, n=7 ---");
        testCase1(solution);

        // 测试2: 示例2 - 3x2网格
        System.out.println("\n--- 测试2: 示例2 m=3, n=2 ---");
        testCase2(solution);

        // 测试3: 示例3 - 7x3网格
        System.out.println("\n--- 测试3: 示例3 m=7, n=3 ---");
        testCase3(solution);

        // 测试4: 示例4 - 3x3网格
        System.out.println("\n--- 测试4: 示例4 m=3, n=3 ---");
        testCase4(solution);

        // 测试5: 最小网格 1x1
        System.out.println("\n--- 测试5: 最小网格 m=1, n=1 ---");
        testMinGrid(solution);

        // 测试6: 单行网格 1xn
        System.out.println("\n--- 测试6: 单行网格 m=1, n=10 ---");
        testSingleRow(solution);

        // 测试7: 单列网格 mx1
        System.out.println("\n--- 测试7: 单列网格 m=10, n=1 ---");
        testSingleColumn(solution);

        // 测试8: 2x2网格
        System.out.println("\n--- 测试8: 2x2网格 m=2, n=2 ---");
        testSmallGrid(solution);

        // 测试9: 较大网格
        System.out.println("\n--- 测试9: 较大网格 m=10, n=10 ---");
        testLargeGrid(solution);

        // 测试10: 长方形网格
        System.out.println("\n--- 测试10: 长方形网格 m=5, n=8 ---");
        testRectangleGrid(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .输入：m = 3, n = 7
     * .期望输出：28
     */
    private static void testCase1(S86_Mid_62_不同路径 solution) {
        int m = 3, n = 7;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 28");
        assert result == 28 : "结果应为 28";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .输入：m = 3, n = 2
     * .期望输出：3
     */
    private static void testCase2(S86_Mid_62_不同路径 solution) {
        int m = 3, n = 2;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 3");
        assert result == 3 : "结果应为 3";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 示例3
     * .输入：m = 7, n = 3
     * .期望输出：28
     */
    private static void testCase3(S86_Mid_62_不同路径 solution) {
        int m = 7, n = 3;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 28");
        assert result == 28 : "结果应为 28";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 示例4
     * .输入：m = 3, n = 3
     * .期望输出：6
     */
    private static void testCase4(S86_Mid_62_不同路径 solution) {
        int m = 3, n = 3;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 6");
        assert result == 6 : "结果应为 6";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 最小网格
     * .输入：m = 1, n = 1
     * .期望输出：1
     */
    private static void testMinGrid(S86_Mid_62_不同路径 solution) {
        int m = 1, n = 1;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 1");
        assert result == 1 : "1x1网格只有1条路径";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 单行网格
     * .输入：m = 1, n = 10
     * .期望输出：1（只能一直向右）
     */
    private static void testSingleRow(S86_Mid_62_不同路径 solution) {
        int m = 1, n = 10;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 1");
        assert result == 1 : "单行网格只有1条路径";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 单列网格
     * .输入：m = 10, n = 1
     * .期望输出：1（只能一直向下）
     */
    private static void testSingleColumn(S86_Mid_62_不同路径 solution) {
        int m = 10, n = 1;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 1");
        assert result == 1 : "单列网格只有1条路径";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 2x2网格
     * .输入：m = 2, n = 2
     * .期望输出：2
     * .解释：右→下 或 下→右
     */
    private static void testSmallGrid(S86_Mid_62_不同路径 solution) {
        int m = 2, n = 2;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 2");
        assert result == 2 : "2x2网格有2条路径";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 较大网格
     * .输入：m = 10, n = 10
     * .期望输出：48620
     * .解释：C(18, 9) = 48620
     */
    private static void testLargeGrid(S86_Mid_62_不同路径 solution) {
        int m = 10, n = 10;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 48620");
        assert result == 48620 : "10x10网格有48620条路径";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 长方形网格
     * .输入：m = 5, n = 8
     * .期望输出：330
     * .解释：C(11, 4) = 330
     */
    private static void testRectangleGrid(S86_Mid_62_不同路径 solution) {
        int m = 5, n = 8;
        System.out.println("输入: m = " + m + ", n = " + n);

        int result = solution.uniquePaths(m, n);

        System.out.println("输出: " + result);
        System.out.println("期望: 330");
        assert result == 330 : "5x8网格有330条路径";
        System.out.println("✓ 测试10通过");
    }
}
